The presumed etiologic agent in the majority of cases of cervical carcinoma is the human papilloma virus. Since this virus produces oncogenic proteins that are foreign to the host, they should be susceptible to the immune system and less likely to escape immune surveillance. HPV, types 16, 18, and 33 are associated with 75-90% of cervical cancers. E6 and E7 are the major transforming proteins and are required for the maintenance of the transformed phenotype. The transforming activity of E6 and E7 is felt to be due to their inhibitory effects on P53 and RB, respectively. Preclinical studies have shown that immunization with non- tumorigenic transfectants expressing E7 and E6 can protect mice from subsequent challenge with tumors expressing these proteins. A live recombinant vaccinia virus HPV construct (TA-HPV) expressing the HPV 16 and 18 E6 and E7 genes will be used in this study. The objectives of this study are: 1) to evaluate the immunological response to this HPV 16/18, E6-E7-vaccinia recombinant; 2) develop data on toxicity; 3) evaluate the local immunological response in pts. with biopsiable disease; 4) evaluate the effect of HLA phenotype on the immunological response, 5) evaluate the environmental safety profile, and 6) determine antitumor activity. Pts. will receive live recombinant vaccinia virus-human papilloma virus vaccine 2.5x106PFU administered percutaneously with scarification in the upper arm every 28 days x 4. 14 pts. have been entered for the study. 12 patients are evaluable. No unexpected adverse events have been seen. Accrual will be limited to a total of 14 evaluable patients. The immunological data will form the basis for future studies.